class Solution {
public:
    typedef long long LL;
    long long maxRunTime(int n, vector<int>& batteries) {
        LL l = 1;
        LL r = 1e9;
        LL ans = 0;
        while (l <= r)
        {
            LL m = l + ((r - l) >> 1);
            if (f(batteries, n, m))
            {
                l = m + 1;
                ans = m;
            }
            else
                r = m - 1;
        }

        return ans;

    }

    bool f(vector<int>& batteries, int num, LL time)
    {
        LL sum = 0;
        for (int i = 0; i < batteries.size(); i++)
        {
            if (batteries[i] > time)
                num--;
            else
                sum += batteries[i];
        }

        if (sum >= num * time)
            return true;

        return false;
    }
};